package cn.xaut.剑指offer.m01;

// 19. 删除链表的倒数第N个节点
public class demo05 {

    // 利用长度的数学关系
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        int size = 0;
        ListNode cur = head;
        while (cur != null) {
            size ++;
            cur = cur.next;
        }

        cur = head;
        for (int i = 1; i <= size - n - 1; i++) 
            cur = cur.next;
        
        cur.next = cur.next.next;
        return head;
    }
    

    // 双指针
    public ListNode removeNthFromEnd2(ListNode head, int n) {

        ListNode fast = head, slow = head;
        for (int i = 0; i < n; i++) 
            fast = fast.next;
        
        if (fast == null)
            return head.next;
        
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        
        slow.next = slow.next.next;
        return head;
    }
}
